The concepts involved in the present invention relate to spread-spectrum communications and particularly to application of matrix processing to a matched-filter, used for example to recognize chip-code sequences within a spread-spectrum signal.
Mobile communication is becoming increasingly popular, at much the same time that more and more customers are asking for ever higher data-rate services. Increasingly, development efforts are focusing on techniques for high-capacity communication of digital information over wireless links.
Spread-spectrum is a method of modulation, like FM, that spreads a data signal for transmission over a bandwidth, which substantially exceeds the data transfer rate. Spread-spectrum is now finding frequent application to wideband communication over wireless links. Direct sequence spread-spectrum involves modulating a data signal with a pseudo-random chip sequence. The spread-spectrum signal is transmitted as a radio wave over a communications media to the receiver. The receiver despreads the signal to recover the information data.
Receiving the spread spectrum communications therefore requires detection of one or more spreading chip-code sequences embedded in an incoming spread-spectrum signal as well as subsequent synchronization of the receiver to the detected chip-code sequence. Initial detection and phase synchronization of the spreading chip code sequence(s) in the receiver is commonly known as code acquisition. Although simple correlators have been used in the code acquisition for reception of spread-spectrum signals, faster and more effect techniques for code acquisition rely on matched filters.
A matched filter essentially matches an input signal to a reference chip-code sequence signal, by multiplying a set of N samples of the input signal with the reference signal, then summing the product terms to determine a value of correlation of the input signal to the reference signal. If the correlation value exceeds a threshold, then a decision circuit indicates that there is a match. A bank of matched filters may process the input in parallel, to determine the correlation to a plurality of codes. The reference code having the highest correlation with the input is selected as the match to the code contained in the received spread spectrum signal.
Although the matched filter is an effective technique for detecting a code sequence within a received spread-spectrum signal, implementation for detecting a number of possible codes may be quite hardware intensive. Particularly for relatively long chip code sequences, each of the matched filters in a bank of filters requires a large number of adders in the form of an extensive adder tree, to complete the computation of the correlation value for use in determining if there is a match to the reference chip-code sequence signal.
To appreciate the problem, it may be helpful to consider some examples. FIG. 1 shows an example of a matched filter bank 11 for detecting a plurality of 1 to N chip-code sequences. An analog to digital converter (not shown) digitizes a received spread-spectrum signal. The resulting input signal with K bits is sequentially input to a tapped delay line. The delay line essentially comprises N delay devices 13 with a tap before the first delay device, taps between the delay devices, and a tap after the last delay device as shown. Each matched filter 15 receives the same inputs, specifically the input signal as well as the delayed input from each output of a delay device 13 in the line. However, each filter receives a different chip-code sequence for use as a reference and therefore attempts to recognize a different code sequence within the bit stream derived from the received spread-spectrum signal.
Each filter 15 outputs a correlation value m(k). Because there are K bits in the input sample, each output m will include K+L bits, where L is the number of layers within the filters 15. Overall the filter bank 11 will produce a matrix of correlation values m1(k),m2(k) . . . mNxe2x88x921(k).
FIG. 2 is a block diagram useful in understanding the implementation of one of the matched filters 15. Specifically, the block diagram shows one L-layered structure for performing the matched filter function. The matched filter comprises a plurality of multipliers 17. The filter includes one such multiplier 17 for receiving each of the input bit sequences from the input and the taps between the delays 13 of the delay line. Assume for discussion purposes that each reference code comprises a sequence Si,0 Si,1 . . . Si,N S0,Nxe2x88x921. The first code sequence, for example, would be S0,0 S0,1 . . . S0,N S0,Nxe2x88x921. Each multiplier therefore receives a portion of reference code sequence Si,0 Si,1 . . . Si,N S0,Nxe2x88x921 for multiplication with the respective delayed portion of the input bit stream r.
Assuming that a code bit may have a value of 1 or xe2x88x921 (corresponding to 0, 1 in digital notation), each multiplication operation will have an output value of 1 if the input value and the reference value are the same (1x1 or xe2x88x921xxe2x88x921). Each multiplication operation will have an output value of xe2x88x921 if the input value and the reference value are different (1xxe2x88x921 or xe2x88x921x1). To determine an overall correlation to the complete reference code, the outputs of the multipliers are summed in pairs, through layers of adders 19, 20, and 21. The last adder 21 outputs the total correlation value, which represents how closely the input bit stream matched the reference sequence. For a perfect match, for example, the output of the adder 21 would be N. If there is no match at all, the output of the adder 21 would be 0. However, in an implementation processing real received spread-spectrum signals, there will be some variable degree of matching.
Returning to FIG. 1, each matched filter will output a value m(k) representing the degree of correlation between the input and the respective reference chip-code sequence. A decision element, not shown compares the output of each matched filter 15 to a threshold and/or to the values from the other filters to determine the most likely match to one of the reference code sequences.
With this type of matched filter approach, assume for discussion that the input has K bits, and the orthogonal signal set is of 64 Walsh codes with any cover code of a length of 64. The receiver would require a bank having 64 matched filters. Each matched filter would have:
Totally, there would 64(63K+57)=4032K+3,648 of bit addition operations. When K=4, the receiver would require (4,032(4)+3,648) of bit additions, that is to say 19,776 of bit additions. If K=8, then the receiver actually would require (4,032(8)+3,648) of bit additions, that is to say 35,904 of bit additions. Although these additions may be implemented in software, for spread-spectrum receivers, they are typically implemented as hardware in an ASIC. Each adder consumes space on the actual chip. Each adder increases the complexity of design and manufacture of the chip. Also, each adder requires additional power, which is a particularly scarce resource in a mobile wireless receiver.
Hence there is a clear need for a technique to reduce the computations and thus the amount of hardware needed to implement the matched filter bank in a spread-spectrum receiver.
Accordingly, a general objective of the invention is to achieve improved processing in a matched filter-bank, typically for use in a receiver for spread-spectrum signal processing, to enable accurate code detection with substantially reduced numbers of computations and thus with reduced requirements for hardware.
Another objective relates to use of matrix processing to allow code detection on a smaller portion of a code matrix, and thus on a reduced matrix of code elements. Assuming a known relationship of the detectable code elements to the other elements of the code matrix, it is possible to detect the more limited portion of the matrix and extrapolate to complete the matrix of detected signals.
The inventive concepts alleviate the above noted problems in spread-spectrum communications and achieve the stated objectives by using spreading codes having a known desired degree of orthogonal relationship or manipulating input signals and reference signals to conform to the desired relationship. The code relationship enables separate matching of portions of the input matrix to a selected subset of the reference code matrix. Manipulation of the resulting sub-matrices of correlation values enables determination of the overall correlations of the input to the full matrix of reference codes.
One aspect of the present invention therefore relates to a matched filter bank for processing spreading codes in a signal received from a spread-spectrum communication system. The matched filter bank utilizes two quadrant matrix matched filters. The first quadrant matrix matched filter receives a first half of an input bit stream, derived from the received spread-spectrum signal. The first quadrant matrix matched filter derives a first quarter matrix of correlation values, which represent the correlation of the first half of the input bit stream to a first quadrant of a matrix of reference codes related to the possible spreading codes utilized in the spread-spectrum communication system. In accord with the invention, the codes of the reference matrix exhibit at least a predetermined degree of orthogonality to other codes within the matrix. The second quadrant matrix matched filter similarly processes the second half-matrix of the input bit stream and a second quadrant of the matrix of reference codes to produce a second quarter matrix of correlation values.
It is understood that a matrix is an xe2x80x9corthogonal matrixxe2x80x9d if every row is orthogonal to every other row. The inventive matched filter techniques may use an orthogonal reference matrix, however, the preferred embodiments work with any reference matrix wherein each row of the upper half of the matrix is orthogonal to the corresponding row of the lower half of the matrix.
The filter bank also includes a matrix computation system. This system manipulates the first quarter matrix of correlation values and the second quarter matrix of correlation values, to obtain a full matrix of correlation values representing correlation of the bit stream to the entire orthogonal matrix of reference codes.
In a preferred embodiment, the matrix computation system comprises a matrix adder and a matrix subtractor. The matrix adder adds the first and second quarter matrices of correlation values together, and the subtraction circuit subtracts the second quarter matrix of correlation values from the first quarter matrix of correlation values. The outputs of the matrix adder and the matrix subtractor together form the full matrix of correlation values.
In some cases, the actual spreading codes utilized in the spread-spectrum communication system have the desired orthogonal property, enabling use of a matrix of the actual spreading codes directly as the matrix of reference codes. In such a case, there is a one-to-one relationship between the spreading codes used in the spread-spectrum communication system and the codes making up the orthogonal reference matrix.
However, in some cases there is a different relationship between the spreading codes and the matrix of reference codes. If the spreading codes used in the spread-spectrum communication system are not sufficiently orthogonal or do not otherwise have the desired property, it is possible to determine a matrix relationship between the spreading codes and the desired matrix of reference codes. In such a case, the invention relies on matrix manipulation of the input bit stream and/or elements in the various quadrants of the matrix of spreading codes, to effectuate a conversion corresponding to a conversion of a matrix of the possible spreading codes to the matrix of reference codes having the desired property.
Aspects of the invention also include use of the inventive matched filter bank in a spread spectrum receiver. In such an implementation, the receiver includes an analog to digital converter for converting a received spread-spectrum signal to a digital bit stream comprising a matrix of input samples. The two quadrant matrix matched filters receive and process the separate halves of the input matrix, to produce the two quadrants of the matrix of correlation values and derive the overall correlation matrix therefrom. The receiver also includes a processor for receiving the full matrix of correlation values. The processor analyzes the values from that matrix to identify a code contained within the received spread-spectrum signal, by identifying one of the reference codes corresponding to the highest correlation value in the full matrix of correlation values.
Another aspect of the invention relates to a method of processing spreading code sequences in a signal received from a wireless spread-spectrum communication system. The method entails establishing an orthogonal matrix of reference code sequences. Each reference code sequence in the orthogonal matrix has a known relationship to one of the spreading code sequences that may be in the signal received from the wireless spread-spectrum communication system. A first one of four quadrants of the orthogonal matrix serves as a first quadrant reference matrix, and a second one of the four quadrants of the orthogonal matrix serves as a second quadrant reference matrix. The received signal is converted into a digital bit stream, and a predetermined number of samples from the digital bit stream are processed to form a matrix input, which is separated into a first half matrix and a second half matrix. The method involves two matched-filtering steps. The first such filtering step processes the first half matrix and the first quadrant reference matrix, to derive a first quarter matrix of correlation values. The second filtering step processes the second half matrix and the second quadrant reference matrix, to derive a second quarter matrix of correlation values. The methodology also entails processing the first and second quarter matrices of the correlation values, to obtain a full matrix of correlation values. The full matrix of correlation values represents correlation of the predetermined number of samples from the digital bit stream to the entire orthogonal matrix of reference code sequences.
The inventive matrix processing in the matched filter bank substantially reduces the complexity and amount of computation needed to derive the full set of correlation values. If the matching were done in a processor, this would reduce the number of overall calculations that the processor must perform. However, in a device for use in a mobile wireless receiver, the code matching function typically is executed by hardware. In this later case, the matrix processing in accord with the invention enables a substantial reduction in the necessary hardware.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following and the accompanying drawings or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.